package eerbaar.shared.tree;

import java.util.Iterator;
import java.util.Stack;

class Momento {

    int index;

    INode node;

    public Momento(INode node) {
        this.node = node;
    }

    public Momento(Momento copy) {
        this.node = copy.node;
        this.index = copy.index;
    }

    @Override
    public String toString() {
        return this.node.getPayload().getKey() + "(" + index + ")";
    }

}

public class NodeIterator implements Iterator<NodeIterator.Result> {

    public static class Result {

        public final int depth;

        public final INode node;

        public Result(INode node, int depth) {
            this.depth = depth;
            this.node = node;
        }

        @Override
        public String toString() {
            return "" + node + "(" + depth + ")";
        }

    }

    private final Stack<Momento> stack = new Stack<Momento>();

    private boolean isStart = true;

    public NodeIterator(INode start) {
        assert (start != null);

        this.stack.add(new Momento(start));
    }

    public INode getParent() {

        INode result = null;
        if (this.stack.size() > 1) {
            Momento momento = this.stack.elementAt(this.stack.size() - 2);
            result = momento.node;
        }

        return result;
    }

    @Override
    public boolean hasNext() {

        Stack<Momento> copy = new Stack<Momento>();
        for (Momento momento : this.stack) {
            copy.add(new Momento(momento));
        }

        Result result = NodeIteratorUtil.next(copy, isStart);
        return (result != null);
    }

    @Override
    public NodeIterator.Result next() {

        NodeIterator.Result result = NodeIteratorUtil.next(stack, isStart);
        isStart = false;
        return result;
    }

    @Override
    public void remove() {

        throw new UnsupportedOperationException();
    }

}

class NodeIteratorUtil {

    public static NodeIterator.Result next(Stack<Momento> stack, boolean isStart) {

        NodeIterator.Result result = null;

        do {

            if (stack.size() == 0) {

                break;
            }

            Momento current = stack.peek();

            if (isStart) {

                result = new NodeIterator.Result(current.node, 0);
                break;
            }

            if (current.index < current.node.getChildCount()) {

                INode child = current.node.getChild(current.index);
                result = new NodeIterator.Result(child, stack.size());
                current.index++;

                stack.push(new Momento(child));
                break;
            }

            stack.pop();
            while (stack.size() > 0) {

                current = stack.peek();

                if (current.index >= current.node.getChildCount()) {
                    stack.pop();
                }

                break;
            }

        } while (true);

        return result;
    }
}
